package com.gitee.feizns.explore.data_structure.tree.bs.easy;

/**
 * @author feizns
 * @since 2019/12/25
 */
public class LowestCommonAncestor {

    public static void main(String[] args) {
        TreeNode node = create();
        System.out.println(lowestCommonAncestor(node, node.left, node.left.right).val);
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(6);
        ret.left = new TreeNode(2);
        ret.right = new TreeNode(8);
        ret.left.left = new TreeNode(0);
        ret.left.right = new TreeNode(4);
        ret.left.right.left = new TreeNode(3);
        ret.left.right.right = new TreeNode(5);
        ret.right.left = new TreeNode(7);
        ret.right.right = new TreeNode(8);
        return ret;
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int val = root.val;
        if ( p.val > val && q.val > val )
            return lowestCommonAncestor(root.right, p, q);
        else if ( p.val < val && q.val < val )
            return lowestCommonAncestor(root.left, p, q);
        return root;
    }

//    private Stack<TreeNode>[] path(TreeNode root, TreeNode p, TreeNode q) {
//
//    }

}
